#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

void test_vector1()
{
	vector<int> V;
	V.push_back(1);
	V.push_back(2);
	V.push_back(3);
	V.push_back(4);
	V.push_back(5);

	for (auto e : V)
	{
		cout << e << ' ';
	}
	cout << endl;

	for (int i = 0; i < V.size(); i++)
	{
		++V[i];
	}

	for (auto e : V)
	{
		cout << e << ' ';
	}
	cout << endl;

	vector<int>::iterator pos = find(V.begin(), V.end(), 10);
	if (pos != V.end())
	{
		V.insert(pos, 0);
	}
	for (auto e : V)
	{
		cout << e << ' ';
	}
	cout << endl;

}


void test_vector2()
{
	vector<int> V;
	V.push_back(1);
	V.push_back(2);
	V.push_back(3);
	V.push_back(8);
	V.push_back(50);
	V.push_back(4);
	V.push_back(60);

	for (auto e : V)
	{
		cout << e << ' ';
	}
	cout << endl;
	//升序
	sort(V.begin(), V.end());
	for (auto e : V)
	{
		cout << e << ' ';
	}
	cout << endl;
	//降序——仿函数greater匿名对象
	sort(V.begin(), V.end(), greater<int>());
	for (auto e : V)
	{
		cout << e << ' ';
	}
	cout << endl;

	vector<string> strV;
	//push_back参数用引用，防止拷贝构造深拷贝。传值会深拷贝代价太大。
	string s1 = "李四";
	strV.push_back(s1);
	strV.push_back(string("王五"));
	strV.push_back("张三");//在构造函数隐式类型转化const char* ->

	//加引用防止深拷贝
	for (const auto& str : strV)
	{
		cout << str << endl;
	}



}

void test_vector3()
{
	vector<int> V;
	V.push_back(1);
	V.push_back(2);
	V.push_back(3);
	V.push_back(8);
	V.push_back(50);

	vector<int>::iterator pos = find(V.begin(), V.end(), 3);

	if (pos != V.end())
	{
		V.insert(pos, 10);
	}

	for (auto e : V)
	{
		cout << e << ' ';
	}
	cout << endl;

	pos = find(V.begin(), V.end(), 3);


	if (pos != V.end())
	{
		V.erase(pos);
	}

	for (auto e : V)
	{
		cout << e << ' ';
	}
	cout << endl;
}

void test_vector4()
{
	vector<int> V;
	V.push_back(1);
	V.push_back(2);
	V.push_back(3);
	V.push_back(8);
	V.push_back(50);
	V.push_back(4);
	V.push_back(6);
	V.push_back(9);

	sort(V.begin(), V.end());

	for (auto e : V)
	{
		cout << e << ' ';
	}
	cout << endl;

	sort(V.begin(), V.end(),greater<int>());

	for (auto e : V)
	{
		cout << e << ' ';
	}
	cout << endl;
}

//26.删除有序数组中重复项
//https://leetcode.cn/problems/remove-duplicates-from-sorted-array/submissions/
//class Solution {
//public:
//	int removeDuplicates(vector<int>& nums) {
//		int src = 0;
//		int next = 1;
//		while (next < nums.size())
//		{
//			if (nums[next] == nums[src])
//			{
//				next++;
//			}
//			else
//			{
//				nums[++src] = nums[next++];
//			}
//		}
//
//		nums.resize(src + 1);
//		return src + 1;
//	}
//};



//int main()
//{
//
//	/*test_vector4();*/
//
//	vector<int> T = { 0,0,1,1,1,2,2,3,3,4 };
//	for (auto e : T)
//	{
//		cout << e << ' ';
//	}
//	cout << endl;
//	Solution().removeDuplicates(T);
//	for (auto e : T)
//	{
//		cout << e << ' ';
//	}
//	cout << endl;
//	return 0;
//}

//17.电话号码的字母组合
//https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
const char* numTostr[10] = { " "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };

class Solution {
	//string numTostr[10] = { " "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
public:
	void Combine(string digits, int x, vector<string>& V, string str)
	{
		if (x == digits.size())
		{
			V.push_back(str);
			//显示组合
			//for (auto e : V)
			//{
			//	cout << e << ' ';
			//}
			//cout << endl;
			return;
		}
		//获取映射数字
		int num = digits[x] - '0';
		string s = numTostr[num];
		for (auto ch : s)
		{
			Combine(digits, x + 1, V, str + ch);
		}
	}
	vector<string> letterCombinations(string digits) {
		vector<string>V;
		if (digits.empty())
		{
			return V;
		}
		string s;
		Combine(digits, 0, V, s);
		return V;
	}
};

int main()
{
	Solution().letterCombinations("23");

	return 0;
}